package com.longshine.arthmetic.ai;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 人工智能之A*算法
 *  
 *
 * @classname   AStart.java 
 * @author      YitianC
 * @version     Revision: 1.1,  Date: 2008/05/14 01:43:47  
 * @history     
 *              Apr 23, 2012 1:56:01 PM  
 *
 */
public class AStart {

	private Point startLoca; //开始位置
	private Point dest;			//结束位置
	private Map2D map;			//地图
	private List<Point> openTable = new LinkedList<Point>(); //open表，用于存放候选位置
	private List<Point> closeTable = new LinkedList<Point>();	//close表，用于存放已经超过的位置
	private Point cur ;				//当前位置
	public AStart(Map2D map){
		this.map = map;
	}
	public static void main(String[] args){
		Map2D m = new Map2D(new int[][]{
				{0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0},
				{0,0,1,1,1,1,0,0,0,0},
				{0,0,0,0,0,1,0,0,0,0},
				{0,0,0,0,0,1,0,0,0,0},
				{0,0,0,0,0,1,0,0,0,0},
				{0,0,1,1,1,1,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0}
		});
		AStart as = new AStart(m);
		as.setStartLoca(new Point(2,4));
		as.setDest(new Point(8,4));
		System.out.println(as.findBestPath());
	}
	/**
	 * 
	 * 向l中加入p,当前点和当前点的父结点形成的链表组成了最短路径 
	 * 
	 * @param l
	 * @param p
	 * @author      YitianC 
	 * @history 
	 *              YitianC Apr 24, 2012 3:27:21 PM
	 */
	public void addPath(List<Point> l,Point p){
		if(p.parent!= null){
			addPath(l,p.parent);
		}
		l.add(p);
	}
	/**
	 * 
	 * 找到最短路径 
	 * 
	 * @return
	 * @author      YitianC 
	 * @history 
	 *              YitianC Apr 24, 2012 3:29:21 PM
	 */
	public List<Point> findBestPath(){
		cur = startLoca;
		closeTable.add(startLoca);
		while(!cur.equal(dest)){
			Point sur[] = this.getSurroundPoints(cur) ;
			if(sur.length==0){
				this.removePoint(openTable, cur.x, cur.y);
				cur = this.getBestPoint();
			}
			else{
				for(Point c:sur){
					//计算f_func;
					openTable.add(c);
					c.parent = cur;
				}
				openTable.remove(cur);
				closeTable.add(cur);
				cur = this.getBestPoint();
			}
		}
		List<Point> rt = new ArrayList<Point>();
		this.addPath(rt, cur);
		clearMemory();
		return rt;
	}
	/**
	 * 
	 * 清除内存空间 
	 * 
	 * @author      YitianC 
	 * @history 
	 *              YitianC Apr 24, 2012 3:29:52 PM
	 */
	public void clearMemory(){
		for(Point p:openTable){
			p.parent = null;
		}
		openTable.clear();
		openTable = null;
		for(Point p:closeTable){
			p.parent = null;
		}
		closeTable.clear();
		closeTable = null;
	}
	/**
	 * 
	 * 在候选点表(open)中找到消耗最小的点 
	 * 
	 * @return
	 * @author      YitianC 
	 * @history 
	 *              YitianC Apr 24, 2012 3:30:20 PM
	 */
	public Point getBestPoint(){
		Point rt = null;
		int k = 0;
		for(Point p:openTable){
			if(k == 0 &&f_func(p)>=0){
				rt = p;
				k++;
			}
			if(f_func(p)>= 0 &&map.getPointData(p)<map.getPointData(rt)){
				rt = p;
			}
		}
		return rt;
	}
	/**
	 * 
	 * 从l中清除点(x,y) 
	 * 
	 * @param l
	 * @param x
	 * @param y
	 * @author      YitianC 
	 * @history 
	 *              YitianC Apr 24, 2012 3:31:20 PM
	 */
	public void removePoint(List<Point> l,int x,int y){
		for(Point p:l){
			if(p.x == x&&p.y==y){
				p.parent = null;
				l.remove(p);
				return;
			}
		}
	}
	/**
	 * 
	 * 查询l中是否存在点(x,y) 
	 * 
	 * @param l
	 * @param x
	 * @param y
	 * @return
	 * @author      YitianC 
	 * @history 
	 *              YitianC Apr 24, 2012 3:31:43 PM
	 */
	public boolean hasPoint(List<Point> l,int x,int y){
		for(Point p:l){
			if(p.x == x&&p.y==y){
				return true;
			}
		}
		return false;
	}
	/**
	 * 
	 * 在l中找到(x,y)点，并返回 
	 * 
	 * @param l
	 * @param x
	 * @param y
	 * @return
	 * @author      YitianC 
	 * @history 
	 *              YitianC Apr 24, 2012 3:32:09 PM
	 */
	public Point getPoint(List<Point > l,int x,int y){
		for(Point p:l){
			if(p.x == x&&p.y==y){
				return p;
			}
		}
		return null;
	}
	/**
	 * 
	 * 得到loc点周围的可选点 
	 * 
	 * @param loc
	 * @return
	 * @author      YitianC 
	 * @history 
	 *              YitianC Apr 24, 2012 3:32:31 PM
	 */
	public Point[] getSurroundPoints(Point loc){
		List<Point> l = new ArrayList<Point>();
		int lx = map.getXLength();
		int ly = map.getYLength();
		int tx = loc.x+1;
		int ty = loc.y;
		/**
		 * 只有上下左右四个方向的点
		 */
		if(tx<lx){
			if(map.getPointData(tx, ty)==0){
				if(!this.hasPoint(openTable, tx, ty) && !this.hasPoint(closeTable, tx, ty)){ 
					l.add(new Point(tx,ty));
				}
			}
		}
		tx = loc.x-1;
		ty = loc.y;
		if(tx>=0){
			if(map.getPointData(tx, ty)==0){
				if(!this.hasPoint(openTable, tx, ty) && !this.hasPoint(closeTable, tx, ty)){ 
					l.add(new Point(tx,ty));
				}
			}
		}
		tx = loc.x;
		ty = loc.y+1;
		if(ty<ly){
			if(!this.hasPoint(openTable, tx, ty) && map.getPointData(tx, ty)==0){
				if(!this.hasPoint(closeTable, tx, ty)){ 
					l.add(new Point(tx,ty));
				}
			}
			
		}
		tx = loc.x;
		ty = loc.y-1;
		if(ty>=0){
			if(!this.hasPoint(openTable, tx, ty) && map.getPointData(tx, ty)==0){
				if(!this.hasPoint(closeTable, tx, ty)){ 
					l.add(new Point(tx,ty));
				}
			}
		}
		Point[] rt = new Point[l.size()];
		return l.toArray(rt);
	}
	public Point getStartLoca() {
		return startLoca;
	}
	
	public int h_func(Point p){
		return h_func(p.x,p.y);
	}
	public int f_func(Point p){
		
		return h_func(p)+g_func(p);
	}
	public int g_func(Point p){
		return g_func(p.x,p.y);
	}
	public int h_func(int x,int y){
		return (int)Math.sqrt((x-dest.x)*(x-dest.x)+(y-dest.y)*(y-dest.y))*10;
		
	}
	/**
	 * 
	 * f函数 
	 * 
	 * @param x
	 * @param y
	 * @return
	 * @author      YitianC 
	 * @history 
	 *              YitianC Apr 24, 2012 3:33:04 PM
	 */
	public int f_func(int x,int y){
		return h_func(x,y)+g_func(x,y);
	}
	public int g_func(int x,int y){
		return (int)Math.sqrt((x-cur.x)*(x-cur.x)+(y-cur.y)*(y-cur.y))*10;
	}
	public void setStartLoca(Point startLoca) {
		this.startLoca = startLoca;
	}
	public Point getDest() {
		return dest;
	}
	public void setDest(Point dest) {
		this.dest = dest;
	}
	public Map2D getMap() {
		return map;
	}
	public void setMap(Map2D map) {
		this.map = map;
	}
}
